In the field of data communications, it is known to communicate data from a source node to a destination node in accordance with a number of known communications protocols. In this respect, datagrams flow through one or more communications networks, for example the Internet, between the source and the destination nodes, in order to communicate information between the source and destination nodes.
Typically, communications networks support different types of services, some of which is delay tolerant and some of which are delay intolerant. Examples of delay intolerant services include: real-time streaming multimedia applications, such as Voice-over-Internet Protocol (VoIP) services, on-line gaming services or Internet Protocol (IP)-Television (IP-TV) services. Without proper prioritisation and shaping of traffic associated with these services, network congestion is likely to occur, because network capacity is typically a limited resource, and for some networks is insufficient, for example wireless communications networks, such as cellular communications networks.
Resource reservation control mechanisms are therefore implemented in order to maintain Quality of Services (QoS) guarantees for certain types of services supported by the communications network. In this regard, the mechanisms provide different priorities to different applications, users, and/or data flows. In respect of data flows, the mechanisms can support guarantees of certain levels of performance, for example in relation to a required bit rate, delay, jitter, packet-drop probability and/or Bit Error Rate (BER).
Consequently, in order to support the above-mentioned resource reservation mechanisms, network equipment, for example routers located throughout a network, are configured to support traffic shaping. Of course, in order to support uniformity of application of the resource reservation control mechanisms, a number of policies have been developed amongst equipment manufacturers and other interested parties in the Internet community in relation to handling of traffic according to profiles assigned to different types of flows of traffic, for example as specified in Request For Comments (RFC) 2697, RFC 2698, and RFC 4115.
For these and other policies, it is known to implement so-called “token buckets”, which is, generally speaking, a control mechanism that determines when traffic can be transmitted. In this regard, a conceptual container or bucket that can hold tokens is implemented, the tokens representing a unit of bytes or a single packet. A correspondence therefore exists between a number of tokens and the transmission of a packet.
When sufficient tokens are present in the bucket, traffic relating to a flow of data can be transmitted, but when there are no or insufficient tokens in the bucket, traffic can not be transmitted. In this respect, when traffic is transmitted, the bucket is decremented in accordance with the amount of data transmitted. However, the bucket is also replenished at a constant rate until the bucket is full.
When implementing the token bucket, it is known to provide a common time base, a shared computation unit and shared data storage, for example a Random Access Memory (RAM). These shared resources are used to manage a very large number of separate data flows having respective profiles associated therewith. For each profile, one or more token buckets can be employed, depending upon whether the profile concerns support for a single or multiple data rates. Indeed, the shared resources are capable of supporting a wide range of traffic rates from less then a packet per second up to multi-Gigabit per second traffic by different representation of the common time base and the bucket status.
Consequently, a large number of token buckets need to be employed and it can be seen that the shared computation unit and shared RAM cannot update all buckets by at a constant rate in accordance with a classic token bucket algorithm. In this respect, when the RAM is large in order to store token bucket-related data for a large number of flows, an increment of one token every 1/R period is not feasible, because it is not possible to update every token bucket at every 1/R interval for each token bucket due to access time limitations of the RAM. In order to maintain accuracy, particularly in relation to high data rate flows, it is necessary to represent and store timestamp data, statuses of buckets and data rates as non-integer numbers, requiring the RAM to have a sufficiently large capacity in order to store, for example floating point values. When implemented in hardware, the large capacity requirement of the RAM translates into increased die space on an Integrated Circuit (IC), which attracts greater power consumption by the device as well as increased access times. In this regard, wide counters, for example 64 bit counters are typically required. Where floating point arithmetic is employed, which is the preferred type of arithmetic for embedded software that runs on integer cores, large and complex computation logic is required in order to perform calculations.